import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/*
 * @lc app=leetcode.cn id=40 lang=java
 *
 * [40] 组合总和 II
 */

// @lc code=start
class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);//升序
        dfs(candidates, target, 0, 0);
        return res;
    }

    public void dfs(int[] candidates,int target, int sum, int startIndex){
        if(sum>target){
            return;
        }
        if(sum==target){
            res.add(new LinkedList<>(path));
            return;
        }
        for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){
           if(i>startIndex){
                if(candidates[i]==candidates[i-1]){
                    continue;//跳过同一层相同元素，因为同一层相同的话，前面的结果中就包含了后面相同元素继续搜索下去的结果了
                }
           }
           sum+=candidates[i];
           path.add(candidates[i]);
           dfs(candidates, target, sum, i+1);//数枝上面每个元素只选一次
           sum-=candidates[i];
           path.removeLast();
        }
    }
}
// @lc code=end

